/**
 * ymm56.com Inc.
 * Copyright (c) 2013-2021 All Rights Reserved.
 */
package com.algorithm.array.sort;

/**
 * 动态规划-求最大子数组的最大和
 *
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 *
 *
 * @author 韩繁文
 * @version $Id: DynamicProgramming.java, v 0.1 2021-05-02 15:20 韩繁文 Exp $$
 */
public class DynamicProgramming {

    public static void main(String[] args) {
        int [] nums = new int []{-2,1,-5,4,-1,2,1,-5,4};
        System.out.println(DPcalculate(nums));
        System.out.println(forCalculate(nums));
    }

    public static int DPcalculate(int [] nums){
        int res = Integer.MIN_VALUE;
        //求一个数组的子数组最大和，那就是求 f(n) = max(f(n-1), f(n-1) + num[n])
        int fn = 0;

        for (int i = 0; i < nums.length; i++) {
            fn = Math.max(nums[i],fn + nums[i]);
            res = Math.max(fn,res);
        }
       return res;
    }

    /**
     * 设定窗口长度为i,i的范围为【0，nums]
     * 子数组窗口，窗口左边[0，nums-i]；窗口右边【i,nums]
     * 暴力循环法
     */
    public static int forCalculate(int [] nums){
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            for(int j = 0; j< nums.length - i;j++){
                int res = 0;
                for (int k = j; k < j+i; k++){
                    res = nums[k] + res;
                    if (res > max ){
                        max = res;
                    }
                }
            }
        }
        return  max;
    }

}
